奇怪小 trick

为了浅显易懂，本文对很多简单的推导都加以说明，尽量减少跳步，尽管有些可能很好想到。所以略显冗长。

已知全集 $U$ 和集合 $X$，且 $n=|U|$。如何高效输出 $X$ 的子集？如何高效输出 $U$ 的所有子集的所有子集？

我们这里用 $[0,2^n-1)$ 的二进制整数来表示一个集合，并且这些整数与集合构成双射（这里我们把集合看做有序的）。具体来说，$X$ 对应整数 $x$，若 $x$ 的第 $i$ 低位为 1，那么元素 $U_i\in X$，否则，$U_i\not\in X$。比如，$(2^n-1)_{10}=(111\dots11)_2$ 对应全集 $U$，而 $x=(10110)_2$ 对应的 $X$ 由 $U_2,U_3,U_5$ 组成。

生成 $X$ 的子集

如何生成？先上代码：

vector<int> generate_sub_set(int x) {
    vector<int> ret;
    for(int p=x;p;p=(p-1)&x) ret.push_back(p);
    ret.push_back(0) // 特殊处理空集
    return ret;
}

每次生成 $O(1)$ 的，而子集数量应是 $2^{\operatorname{popcount}(x)}$ 个，显然复杂度 $O(2^{\operatorname{popcount}(x)})$。（$\operatorname{popcount}(x)$ 指的是 $x$ 二进制位中 $1$ 的数量。）

关键代码就一行，很短，不是吗？

下面来证明这个的正确性（变量沿用上文，$\&$ 符号表示按位与）（这个证法是我自己想的，如果有其它更好证法，欢迎在评论区提出）：

命题1：$p$ 一定是 $x$ 的子集。

证明：我们使用了按位与 $x$ 来保证，存在于 $p$ 中的元素一定存在于 $x$（$1\&1=1$），不存在于 $x$ 不存在于 $p$（$0\&1=0$），而这正是子集的定义。

命题2：枚举过程中不存在重复的集合。

证明：首先我们知道 $a\&b\leq\min\{a,b\}$，因此，$(p-1)\&x<p$。所以 $p$ 严格单调递减，$p$ 不会重复。又由于 $[0,2^n-1)$ 的整数和集合构成双射，枚举出的集合就没有重复。

命题3：枚举过程中不存在遗漏的集合。

证明：根据命题2，由于 $p$ 单调递减，等价于证明，若 $p$ 是当前被枚举到的集合，则 $\forall i\in\Big(\big((p-1)\&x,p\big)\cap\mathbb{Z}\Big)$，$i$ 不是 $x$ 的子集。

设 $l=\operatorname {lowbit}(p)$，即 $p$ 的最低的为 $1$ 的二进制位位数（从低到高位，从 $0$ 开始），比如 $(11000)_2$ 的 $\operatorname{lowbit}$ 为 $3$。那么 $p-1$ 的变化就是末 $l+1$ 位：

这个过程是根据减法的退位得到的，不必再证明了吧。

因而 $(p-1)\&x$ 的后 $l$ 位显然就是 $x$ 的后 $l$ 位了。

因此我们可以只看后 $l$ 位。设 $z$ 为 $x$ 的末 $l$ 位，问题变为 $(z,2^{l+1})$ 内是否有 $z$ 的子集。答案是否定的：任意集合 $y$ 的子集 $s$ 应当满足 $y\&s=s$，又根据 $y\&s\leq \min\{y,s\}$，反证，若 $s>y$，则 $s=y\&s\leq y$，与假设矛盾，因此 $s\leq y$。从而，$(z,2^{l+1})$ 内没有 $z$ 的子集。

命题3得证。

综合上述三个命题，正确性便显然了。

生成 $U$ 的所有子集的所有子集

通过这个方法我们枚举的上限复杂度 $O$ 并不会变，只是下限 $\Omega$ 变了。

那有什么用呢？

当生成 $U$ 的所有子集的所有子集时，这个方法就有时间复杂度上的优势了。

一个暴力的想法是，直接枚举 $u$ 的两个子集，判断是否是 $s\subseteq x$，复杂度 $O((2^n)^2)=O(4^n)$：

for(int x=0,ed=(1<<n);x<ed;++x)
    for(int s=0;s<ed;++s)
        if(s|x==x) cout<<s<<' ';

优化的方法也挺暴力的，就是通过刚才提到的生成子集的方法：

for(int x=0,ed=(1<<n);x<ed;++x) {
    for(int p=x;p;p=(p-1)&x) cout<<p<<' ';
    cout<<0<<' ';
}

复杂度是多少呢？

我们知道中间这个循环是 $O(2^{\operatorname{popcount}(x)})$ 的。我们就是要计算这个：

发现顺序不重要。我们只需要统计对于每个 $c$，$\operatorname{popcount}(x)=c$ 的个数即可。也就是：

$[0,2^n)$ 中 $\operatorname{popcount}(x)=c$ 的个数究竟是多少呢？其实就是在 $n$ 位中选 $c$ 位，即 $\dbinom{n}{c}$。

那么就是：

根据二项式定理，这个式子等于 $(2+1)^n=3^n$。

因此这个做法的复杂度是 $O(3^n)$，优化了不少！

Upd on 2023/7/7

其实这个还有一个证明。很简单。设要求 $B\subseteq A,A\subseteq U$ 的方案数。

对于每一个元素，都只有把它放到 $A$，或把它同时放到 $A,B$，或者都不放三种选择。因此有 $3^n$ 个。